package simple;

import data.ListNode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/6/27 11:54
 */
public class No160_相交链表 {
    public static void main(String[] args) {
        ListNode A = new ListNode(1);
        A.next = new ListNode(2);
        A.next.next = new ListNode(3);
        A.next.next.next = new ListNode(7);

        ListNode B = new ListNode(1);
        B.next = new ListNode(2);
        B.next.next = new ListNode(5);
        B.next.next.next = A.next.next;

        Solution160 solution160 = new Solution160();
        ListNode intersectionNode = solution160.getIntersectionNode(A, B);
        System.out.println();

    }
}

class Solution160 {
    public ListNode getIntersectionNode(ListNode red, ListNode green) {
        //双指针
        //保存
        ListNode redCp = red;
        ListNode greenCp = green;

        while (red != null && green != null) {
            if (red == green) {
                return green;
            }
            //指针分别下移
            red = red.next;
            green = green.next;
            //走到头判断
            //红指针
            if (red == null) {
                //到 greenCp 头
                red = greenCp;
            } else if (green == null) {
                //到 redCp 头
                green = redCp;
            }
        }
        return null;
    }
}

    //public ListNode getIntersectionNode(ListNode red, ListNode green) {
    //    //哈希
    //    Set<ListNode> set = new HashSet<>();
    //    while (red != null) {
    //        set.add(red);
    //        red = red.next;
    //    }
    //    //set已经初始化完毕
    //    while (green != null) {
    //        if (set.contains(green)) {
    //            return green;
    //        }
    //        green = green.next;
    //    }
    //    return null;
    //}


    //public ListNode getIntersectionNode(ListNode red, ListNode green) {
    //    //保存
    //    ListNode greenCp = green;
    //    //暴力法
    //    while (red != null) {
    //        //复原
    //        green = greenCp;
    //        while (green != null) {
    //            if (red == green) {
    //                return red;
    //            }
    //            green = green.next;
    //        }
    //        //指针下移
    //        red = red.next;
    //    }
    //    return null;
    //}